#include<bits/stdc++.h>
using namespace std;
const int N=102;

int colors[N][N];
int v[3][N][N];
int dr[]={0,0,1,-1};
int dc[]={1,-1,0,0};

struct Node{
    int r,c,color,cost;
    Node(){}
    Node(int r_,int c_,int color_,int cost_){
        this->r=r_;
        this->c=c_;
        this->color=color_;
        this->cost=cost_;
    }
    bool operator<(const Node& node) const{
        return cost>node.cost;
    }
};

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(v,0x7f,sizeof(v));
    memset(colors,0,sizeof(colors));
    for(int i=1;i<=m;i++){
        int r,c,k;
        scanf("%d%d%d",&r,&c,&k);
        colors[r][c]=k+1;
    }
    v[colors[1][1]][1][1]=0;
	priority_queue<Node> que;
    que.push(Node(1,1,colors[1][1],0));
    while(!que.empty()){
        Node node=que.top();
        que.pop();
        int r=node.r,c=node.c;
        int co=node.color;
        int cost=node.cost;
        if(cost>v[co][r][c]){
            continue;
        }
        for(int i=0;i<4;i++){
            int r1=r+dr[i];
            int c1=c+dc[i];
            if(r1>n||r1<=0) continue;
            if(c1>n||c1<=0) continue;
            int co1=colors[r1][c1];
            //此处格子无颜色
            if(colors[r][c]==0){
                if(co1==0) continue;
                else if(co1!=node.color){
                    if(v[co1][r1][c1]>v[node.color][r][c]+1){
                        v[co1][r1][c1]=v[node.color][r][c]+1;
                        que.push(Node(r1,c1,co1,v[co1][r1][c1]));
                    }
                }
                else if(co1==node.color){
                    if(v[co1][r1][c1]>v[node.color][r][c]){
                        v[co1][r1][c1]=v[node.color][r][c];
                        que.push(Node(r1,c1,co1,v[co1][r1][c1]));
                    }
                }
            }
            //此处格子有颜色
            else if(colors[r][c]!=0){
                //要去格子 无颜色
                if(colors[r1][c1]==0){
                    int ecolor=colors[r][c];
                    if(v[ecolor][r1][c1]>v[node.color][r][c]+2){
                        v[ecolor][r1][c1]=v[node.color][r][c]+2;
                        que.push(Node(r1,c1,ecolor,v[ecolor][r1][c1]));
                    }
                    int ncolor=(colors[r][c]==1?2:1);
                    if(v[ncolor][r1][c1]>v[node.color][r][c]+3){
                        v[ncolor][r1][c1]=v[node.color][r][c]+3;
                        que.push(Node(r1,c1,ncolor,v[ncolor][r1][c1]));
                    }
                }
                else if(colors[r1][c1]==colors[r][c]){
                    if(v[co1][r1][c1]>v[node.color][r][c]){
                        v[co1][r1][c1]=v[node.color][r][c];
                        que.push(Node(r1,c1,co1,v[co1][r1][c1]));
                    }
                }
                else if(colors[r1][c1]!=colors[r][c]){
                    if(v[co1][r1][c1]>v[node.color][r][c]+1){
                        v[co1][r1][c1]=v[node.color][r][c]+1;
                        que.push(Node(r1,c1,co1,v[co1][r1][c1]));
                    }
                }
            }
        }
    }
    if(v[2][n][n]>40000&&v[1][n][n]>40000) printf("-1");
    else printf("%d",min(v[1][n][n],v[2][n][n]));
    
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    // 	for(int j=1;j<=n;j++){
    // 		printf("%d ",v[0][i][j]);
	// 	}
	// 	cout<<endl;
	// }
	// for(int i=1;i<=n;i++){
    // 	for(int j=1;j<=n;j++){
    // 		printf("%d ",v[1][i][j]);
	// 	}
	// 	cout<<endl;
	// }
    return 0;
}
